/*
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/*
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int x_len=grid.size();
        int y_len=grid[0].size();
        int num=0;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                if(grid[i][j]==1){
                    num=max(num,area(grid,i,j,x_len,y_len));
                }
            }
        }
        return num;
    }    
private:
    int area(vector<vector<int>>& grid,int x,int y,int x_len,int y_len){
        if(x<0||x>=x_len||y<0||y>=y_len||grid[x][y]==0){
            return 0;
        }
        grid[x][y]=0;
        return 1+area(grid,x-1,y,x_len,y_len)+area(grid,x+1,y,x_len,y_len)+area(grid,x,y-1,x_len,y_len)+area(grid,x,y+1,x_len,y_len);
    }
};
*/

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int x_len=grid.size();
        int y_len=grid[0].size();
        int num=0;
        int max_num=0;
        vector<vector<bool>> visited(x_len,vector<bool>(y_len,false));
        vector<vector<int>> direction{{-1,0},{1,0},{0,1},{0,-1}};
        stack<pair<int,int>> dfs;
        bool find_next=false;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                if(grid[i][j]==1&&!visited[i][j]){
                    visited[i][j]=true;
                    dfs.push(make_pair(i,j));
                    num=1;
                    while(!dfs.empty()){
                        int x=dfs.top().first;
                        int y=dfs.top().second;
                        find_next=false;
                        for(auto& dir:direction){
                            int new_x=x+dir[0];
                            int new_y=y+dir[1];
                            if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&grid[new_x][new_y]==1&&!visited[new_x][new_y]){
                                num++;
                                visited[new_x][new_y]=true;
                                dfs.push(make_pair(new_x,new_y));
                                find_next=true;
                            }
                        }
                        if(!find_next){
                            dfs.pop();
                        }
                    }
                    max_num=max(max_num,num);
                }
            }
        }
        return max_num;
    }    
};